|
|
1.
成本控制下的快速影响最大化算法
刘院英, 郭景峰, 魏立东, 胡心专
计算机应用
2017, 37 (2):
367-372.
DOI: 10.11772/j.issn.1001-9081.2017.02.0367
针对成本控制下影响最大化时间复杂度高的问题，提出一种快速的最大化算法BCIM。首先提出对初始节点进行多次传播的传播模型；其次选择高影响力节点作为备用种子，并基于近距离影响减少计算节点影响范围的工作量；最后利用动态规划方法在每组备用种子中最多选择一个种子。仿真实验表明，与随机算法Random、每轮取影响力增量最大的节点的贪心算法Greedy_MII、每轮取影响力增量与成本比值最大的节点的贪心算法Greedy_MICR相比，在影响范围上，BICM接近或优于Greedy_MICR及Greedy_MII，远次于Random；在种子集合的质量上，BCIM、Greedy_MICR、Greedy_MII三者差距较小，但都远远好于Random；在运行时间上，BCIM是Random的几倍，而两个贪心算法都是BCIM的几百倍。BCIM算法能在较短时间内找到更有效的种子集合。
参考文献 |
相关文章 |
多维度评价
|
|
